/**
 *    Copyright (C) 2008  Victor Smirnov <aist11@gmail.com>
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License along
 *    with this program; if not, write to the Free Software Foundation, Inc.,
 *    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 *    See LICENSE.exceptions in the root folder of this project for possible
 *    exceptions
 *
 */


#ifndef __BITVECTOR_TEST_BASE_HPP__
#define __BITVECTOR_TEST_BASE_HPP__

#include <unistd.h>

#include <cppunit/extensions/HelperMacros.h>
#include <cppunit/portability/Stream.h>

#include <cubefs/core/bitvector.hpp>

using namespace cubefs::core::bitvector_ns;
using namespace std;


namespace cubefs {
namespace core {
namespace tests {
namespace bitvector_ns {

class TestBase : public CPPUNIT_NS::TestFixture
{

protected:

    typedef SimplePageManager page_mgr;
    typedef page_mgr::Page        page_t;
    typedef page_mgr::txn_t         txn_t;
    typedef page_mgr::Page::ID    ID;

    typedef bitvector<page_mgr> bv;
    typedef bv::iterator<> iterator;

    typedef bv::tree_node       tree_node;
    typedef bv::node_base       node_base;

    typedef bv::huge_node       huge_node;
    typedef bv::large_node      large_node;
    typedef bv::medium_node     medium_node;
    typedef bv::small_node      small_node;

    typedef bv::root_huge_node       root_huge_node;
    typedef bv::root_large_node      root_large_node;
    typedef bv::root_medium_node     root_medium_node;
    typedef bv::root_small_node      root_small_node;

    typedef bv::bitmap_node     bitmap_node;

    page_mgr mgr;
    txn_t txn;


public:

    TestBase() {}

    void setUp() {
        txn = mgr.begin();
    }

    void tearDown() {
        mgr.commit(txn);
    }

    index_t pow(index_t val, index_t count) {
        index_t result = 1;
        for (int c = 0; c < count; c++) {
            result *= val;
        }
        return result;
    }


    const iterator get_first(node_base *node) {
        while (!node->is_leaf()) {
            node = bv::get_child(node, 0, mgr, txn);
        }
        return iterator(mgr, txn, bv::get_bitmap(node, 0, mgr, txn), 0);
    }

    const iterator get_last(node_base *node) {
        while (!node->is_leaf()) {
            node = bv::get_last_child(node, mgr, txn);
        }
        return iterator(mgr, txn, bv::get_bitmap(node, bv::get_children_count(node) - 1, mgr, txn), 0);
    }

    node_base* create_tree(index_t levels, index_t children, index_t size) {
        return create_tree(levels, children, size, levels);
    }

    node_base* create_tree(index_t levels, index_t children, index_t size, index_t level0) {
        node_base *node = create_node(levels + 1, true);

        __create_tree(node, levels, children, level0);

        iterator iter = get_first(node);

        csize_t prefix = 0;
        csize_t offset = 0;

        do {
            fill_bitmap(iter.data(), prefix, offset, size);
            offset = 0;
        }
        while (iter.next_bitmap());

        return node;
    }

    void fill_bitmap(bitmap_node *bitmap, csize_t &prefix, csize_t &offset, index_t size) {
        bitmap->header().set_size(size);
        bitmap->header().set_rank(0);
        bitmap->header().set_bitsize(size);
        bitmap->header().set_offset(0);
        bitmap->bits().clear();

        bitmap->reindex(prefix, offset, 4, 0);
        update_btree(bitmap, size, 0, size);
    }

    void update_btree(bitmap_node *bitmap, index_t size, index_t rank, index_t bitsize) {
        node_base *node = bv::get_parent(bitmap, mgr, txn);
        bv::update_btree_nodes(node, bitmap->parent_idx(), size, rank, bitsize, mgr, txn);
    }

    node_base *create_node(index_t level, bool root) {
        node_base *node;
        if (level == 1) {
            if (root) {
                root_small_node *_node = new (mgr, txn) root_small_node;
                _node->set_key_size(KEY_SIZE__SMALL);
                node = _node;
            }
            else {
                small_node *_node = new (mgr, txn) small_node;
                _node->set_key_size(KEY_SIZE__SMALL);
                node = _node;
            }
        }
        else if (level == 2) {
            if (root) {
                root_medium_node *_node = new (mgr, txn) root_medium_node;
                _node->set_key_size(KEY_SIZE__MEDIUM);
                node = _node;
            }
            else {
                medium_node *_node = new (mgr, txn) medium_node;
                _node->set_key_size(KEY_SIZE__MEDIUM);
                node = _node;
            }
        }
        else if (level == 3) {
            if (root) {
                root_large_node *_node = new (mgr, txn) root_large_node;
                _node->set_key_size(KEY_SIZE__LARGE);
                node = _node;
            }
            else {
                large_node *_node = new (mgr, txn) large_node;
                _node->set_key_size(KEY_SIZE__LARGE);
                node = _node;
            }
        }
        else {
            if (root) {
                root_huge_node *_node = new (mgr, txn) root_huge_node;
                _node->set_key_size(KEY_SIZE__HUGE);
                node = _node;
            }
            else {
                huge_node *_node = new (mgr, txn) huge_node;
                _node->set_key_size(KEY_SIZE__HUGE);
                node = _node;
            }
        }

        node->level() = level;
        return node;
    }

    void __create_tree(node_base* parent, index_t level, index_t children, index_t level0) {
        BV_NODE_CAST2(parent, {
                index_t children0 = (level > level0 ? 1 : children);
                for (index_t c = 0; c < children0; c++) {
                    tree_node *node;

                    if (level > 0) {
                        node = create_node(level, false);
                        __parent->set_leaf(false);
                        __create_tree((node_base*)node, level - 1, children, level0);
                    }
                    else {
                        __parent->set_leaf(true);

                        node = new (mgr, txn) bitmap_node;

                        node->set_leaf(false);
                        node->set_bitmap(true);
                    }

                    node->parent_idx() = c;
                    node->parent_id() = __parent->id();

                    __parent->map().key(0, c) = 0;
                    __parent->map().key(1, c) = 0;
                    __parent->map().key(2, c) = 0;
                    __parent->map().data(c) = node->id();
                }

                __parent->map().size() = children0;
            }
        );
    }

    csize_t get_key(node_base *node, index_t key) {
        BV_NODE_CAST2(node, return __node->map().max_key(key));
    }

    node_base* get_node(ID &id) {
        return static_cast<node_base*>(mgr.get(txn, id));
    }

    void dump_node(node_base *node, int idx = 0) {
        BV_NODE_CAST2(node, __node->map().dump(idx, cout));
        cout<<"page: "<<node<<" parent: "<<(void*)node->parent_id().value()<<":"<<node->parent_idx()<<" root: "<<node->is_root()<<" leaf: "<<node->is_leaf()<<" level: "<<node->level()<<endl;
    }

    void dump_tree(node_base *node, int idx = 0) {
        dump_node(node, idx);
        for (index_t c = 0; c < bv::get_children_count(node); c++) {
            if (!node->is_leaf()) {
                node_base *node1 = bv::get_child(node, c, mgr, txn);
                CPPUNIT_ASSERT(node1 != NULL);
                dump_tree(node1, idx);
            }
        }
    }

    void remove_tree(node_base *node) {
        for (index_t c = 0; c < bv::get_children_count(node); c++) {
            if (node->is_leaf()) {
                bitmap_node *bitmap = bv::get_bitmap(node, c, mgr, txn);
                mgr.free(txn, bitmap);
            }
            else {
                remove_tree(bv::get_child(node, c, mgr, txn));
            }
        }
        mgr.free(txn, node);
    }

    void check_node(node_base *node, csize_t size, csize_t rank, csize_t bitsize, index_t parent_idx) {

        //cout<<"checking "<<node<<" "<<size<<" "<<rank<<" "<<bitsize<<endl;
        CPPUNIT_ASSERT_EQUAL((index_t)parent_idx, (index_t)node->parent_idx());

        csize_t size0 = 0, rank0 = 0, bitsize0 = 0;
        BV_NODE_CAST2(node,

            CPPUNIT_ASSERT_EQUAL(size,      (csize_t)__node->map().max_key(0));
            CPPUNIT_ASSERT_EQUAL(rank,      (csize_t)__node->map().max_key(1));
            CPPUNIT_ASSERT_EQUAL(bitsize,   (csize_t)__node->map().max_key(2));

            for (index_t c = 0; c < __node->map().size(); c++) {
                index_t size00 = __node->map().key(0, c);
                index_t rank00 = __node->map().key(1, c);
                index_t bitsize00 = __node->map().key(2, c);

                CPPUNIT_ASSERT(size >= 0);
                CPPUNIT_ASSERT(rank >= 0);
                CPPUNIT_ASSERT(bitsize >= 0);

                size0 += size00;
                rank0 += rank00;
                bitsize0 += bitsize00;

                if (!__node->is_leaf()) {
                    node_base * child = bv::get_child(node, c, mgr, txn);
                    check_node(
                        child,
                        size00,
                        rank00,
                        bitsize00,
                        c
                    );
                }
                else {
                    bitmap_node * child = bv::get_bitmap(node, c, mgr, txn);
                    CPPUNIT_ASSERT_EQUAL(size00,    (index_t)child->header().get_size());
                    CPPUNIT_ASSERT_EQUAL(rank00,    (index_t)child->header().get_rank());
                    CPPUNIT_ASSERT_EQUAL(bitsize00, (index_t)child->header().get_bitsize());
                }
            }
        );

        CPPUNIT_ASSERT_EQUAL(size0, size);
        CPPUNIT_ASSERT_EQUAL(rank0, rank);
        CPPUNIT_ASSERT_EQUAL(bitsize0, bitsize);
    }

    void check_bitmaps(iterator &iter, index_t node_bits, index_t data_bits) {
        bool inserted = false, hasnt_label = false;
        csize_t prefix = 0, offset = 0;
        index_t rank, bitsize;

        do {
            CPPUNIT_ASSERT(offset >= (csize_t)iter.data()->header().get_offset());

            index_t size = iter.data()->header().get_size();

            iter.data()->compute_rank_and_size_up_to(
                                        inserted, hasnt_label,
                                        prefix, offset, rank, bitsize,
                                        size, node_bits, data_bits);

            index_t rank0 = 0, bitsize0 = 0;
            for (index_t c = 0; c < iter.data()->header().get_blocks(); c++) {
                rank0       += iter.data()->header().get_rank(c);
                bitsize0    += iter.data()->header().get_bitsize(c);
            }

            CPPUNIT_ASSERT_EQUAL(rank, rank0);
            CPPUNIT_ASSERT_EQUAL(bitsize, bitsize0);

            offset -= size;

            if (rank == bitsize) {
                inserted = inserted || iter.data()->header().get_inserted() >= 0;
                hasnt_label = hasnt_label || (inserted && iter.data()->header().hasnt_label());
            }
            else if (iter.data()->header().get_inserted() >= size - prefix) {
                inserted = true;
                hasnt_label = iter.data()->header().hasnt_label();
            }
            else {
                inserted = hasnt_label = false;
            }

            CPPUNIT_ASSERT_EQUAL(rank, iter.data()->header().get_rank());
            CPPUNIT_ASSERT_EQUAL(bitsize, iter.data()->header().get_bitsize());
        }
        while (iter.next_bitmap());
    }

    void check_tree(node_base *root, csize_t size, csize_t rank, csize_t bitsize, index_t node_bits, index_t data_bits) {
        check_node(root, size, rank, bitsize, 0);
        iterator iter = get_first(root);
        check_bitmaps(iter, node_bits, data_bits);
    }

    template <typename Buffer>
    index_t createUDS(Buffer &page, index_t offset) {
        return createUDS(page, offset, -1);
    }

    template <typename Buffer>
    index_t createUDS(Buffer &page, index_t start, index_t end, index_t offset, index_t label_idx) {
        for (index_t c = 0; c < offset; c++) {
            set_bit(page, c, 0);
        }

        index_t ptr = offset;
        index_t l_idx = 0;

        for (index_t c = start; c < end; c++) {
            for (index_t d = 0; d < c; d++) {
                set_bit(page, ptr++, 1);
            }

            set_bit(page, ptr++, 0);

            for (index_t d = 0; d < c; d++, ptr+=4, l_idx++) {
                if (l_idx != label_idx) {
                    set_bits(page, ptr, 9, 4);
                }
                else {
                    ptr -= 4;
                }
            }

            set_bit(page, ptr++, 0);
        }

        return ptr;
    }

    void fill_bitvector(bv &bv0, index_t start, index_t end_incl) {
        buffer<4096*64> *buf1 = new buffer<4096*64>();
        buf1->clear();

        csize_t size1 = createUDS(*buf1, start, end_incl + 1, 0, -1);

        index_t prefix1 = 0, offset1 = 0, rank1 = 0, bitsize1 = 0;
        compute_rank_and_size_up_to(*buf1, prefix1, offset1, rank1, bitsize1, size1, 4, 0);

        iterator iter(mgr, txn);
        bv0.insert_bitmap_block(iter, *buf1, 0, 0, size1, bv::PATH);

        delete buf1;

        node_base *root = get_node(bv0.root());

        check_node(root, size1, rank1, bitsize1, 0);

        iter = get_first(root);
        check_bitmaps(iter, 4, 0);
    }

    void skip_nodes(iterator &iter, index_t count, index_t node_bits, index_t data_bits) {
        index_t cnt = 0;
        while (cnt < count) {
            CountData data = iter.count_one_fw();
            cnt++;
            if (data.count == 0) {
                iter.move(1);
            }
            else if (data.count == 1) {
                iter.move(1 + node_bits + 1);
            }
            else {
                iter.move(1 + data.count * (node_bits + data_bits) + 1);
            }
        }
    }
};

} //bitvector_ns
} //tests
} //core
} //cubefs

#endif

